package pro.softzhang.algo.lc800;

import pro.softzhang.algo.flag.knowledge.KGraph;

@KGraph
public class LC839_SimilarStringGroups {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int numSimilarGroups(String[] strs) {
            int[] fathers = new int[strs.length];
            for (int i = 0; i < fathers.length; i++) {
                fathers[i] = i;
            }

            int groups = strs.length;
            for (int i = 0; i < strs.length; i++) {
                for (int j = i + 1; j < strs.length; j++)
                    if (similar(strs[i], strs[j]) && union(fathers, i, j))
                        groups--;
            }

            return groups;
        }

        private boolean similar(String str, String str1) {
            int diff = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) != str1.charAt(i))
                    diff++;
            }
            return diff <= 2;
        }

        private boolean union(int[] fathers, int i, int j) {
            int fatherOfJ = findFather(fathers, i);
            int fatherOfI = findFather(fathers, j);
            if (fatherOfI != fatherOfJ) {
                fathers[fatherOfI] = fatherOfJ;
                return true;
            }
            return false;
        }

        private int findFather(int[] fathers, int i) {
            if (fathers[i] != i) {
                fathers[i] = findFather(fathers, fathers[i]);
            }
            return fathers[i];
        }
    }
}
